package com.simon.study.algorithm.zheda;

import com.simon.study.algorithm.tree.TNode;
import com.simon.study.algorithm.tree.Tree;
import com.simon.study.algorithm.tree.TreeTraversal;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.Setter;

/**
 * <p>
 *
 * @author simon
 */
public class LinkTree {

    @NoArgsConstructor @Setter @Getter
    public static class TStack{
        TStack  next;
        TNode   data;

        public TStack(TNode data) {
            this.data = data;
        }
    }

    TStack stack;

    public LinkTree() {
        this.stack = new TStack();
    }

    public boolean empty(){
        return stack.next == null;
    }

    public void push(TNode item){
        TStack tmp  = new TStack(item);
        tmp.next    = stack.next;
        stack.next  = tmp;
    }

    public TNode pop(){
        if(empty()){ return null; }

        TStack first    = stack.next;
        stack.next      = first.next;
        return first.data;
    }


    public void preorder(TNode root){
        TNode node = root;
        while (node != null || !empty()){
            while (node != null){
                push(node);
                System.out.println(node);
                node = node.getLeft();
            }
            if(!empty()){
                node = pop();
                node = node.getRight();
            }
        }
    }

    public void inorder(TNode root){
        TNode node = root;
        while (node != null || !empty()){
            while( node != null ){
                push(node);
                node = node.getLeft();
            }
            if(!empty()){
                node = pop();
                System.out.println(node);
                node = node.getRight();
            }
        }
    }

    public static void main(String[] args) {
        Tree tree = new Tree();

        int[] arr = new int[]{55,66,44,33,11,22,88,99,30,38,28,62};
        // see the tree from the original array.
        tree.setRoot(Tree.createMaxHeapTree(arr));
        tree.hiarachicallyPrint();
        System.out.println();

        TreeTraversal.preorder(tree.getRoot());
        System.out.println();

        LinkTree ltree = new LinkTree();
        ltree.preorder(tree.getRoot());
        System.out.println();

        TreeTraversal.inorder(tree.getRoot());
        System.out.println();

        TreeTraversal.inorderByLoop(tree.getRoot());
        System.out.println();

        TreeTraversal.inorderByLoop2(tree.getRoot());
        System.out.println();

        ltree.inorder(tree.getRoot());
        System.out.println();

        TreeTraversal.postorder(tree.getRoot());
        System.out.println();

        TreeTraversal.postorderByLoop(tree.getRoot());
        System.out.println();
    }
}
